1987D - World is Mine - CodeForces Solution

import math

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    freq = {}
    for i in range(n):
        if a[i] in freq:
            freq[a[i]] += 1
        else:
            freq[a[i]] = 1
    freq_arr = []
    for key in freq:
        freq_arr.append((key, freq[key]))
    freq_arr.sort()
    dp = []
    dp.append([0 for i in range(len(freq_arr))])
    for i in range(len(freq_arr)//2):
        dp.append([float('inf') for j in range(len(freq_arr))])
    for i in range(1, len(dp)):
        for j in range(1, len(dp[0])):
            if not math.isinf(dp[i-1][j-1]):
                if i-1 + freq_arr[j][1] + dp[i-1][j-1] <= j:
                    dp[i][j] = min(dp[i][j-1], freq_arr[j][1] + dp[i-1][j-1])
                else:
                    dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] = dp[i][j-1]
    
    remove = 0
    for i in range(1, len(dp)):
        if not math.isinf(dp[i][-1]):
            remove = i
            print(len(freq_arr) - remove)